/**
 * 快速排序算法,平均时间复杂度为O(nlgn),最坏情况为O(n^2)
 * @author firebroo
 *
 */
public class QuickSortTest {

	/**
	 * 快速排序算法实现
	 */
	private static int getMiddle(int[] data, int low,int high){
		int tmp=data[low];                                                  //一般选择数组的第一个元素作为初始枢轴
		while(low < high){                                              
			while(low < high && data[high] >= tmp){                     //从右边扫描比tmp小的元素
				high--;
			}
			data[low]=data[high];                                       //成功就把元素移动到tmp的前面
			while(low < high && data[low] <= tmp){                      //从左边扫描比tmp大的元素
				low++;
			}
			data[high]=data[low];                                       //成功就把元素移动到tmp的后面
		}
		data[low]=tmp;                                                      //循坏结束，将tmp插入两个子数组的中间，此时左边的元素都小于tmp，右边的元素都大于tmp
		return low;
	}
	
	/**
	 * 递归调用
	 */
	private static void _quickSort(int[] data, int low, int high){
		if(low < high){
			int middle=getMiddle(data,low,high); 
			_quickSort(data,low,middle-1);  
			_quickSort(data,middle+1,high);
		}
	}
	
	/**
	 * 算法测试
	 */
	public static void main(String[] args){
		int[] data={20,22,3,3,34,5,6,44};
		_quickSort(data,0,data.length-1);
		for(int i=0;i<data.length;i++){
			System.out.println(data[i]);
		}
	}
}
